package _11_整理题目._6_模拟设计._多数之和;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/pairs-with-sum-lcci/
 *
 * 设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。
 *
 * 输入: nums = [5,6,5], target = 11
 * 输出: [[5,6]]
 *
 * 输入: nums = [5,6,5,6], target = 11
 * 输出: [[5,6],[5,6]]
 *
 * 思路：排序 + 双指针
 *
 */
public class _011_数对之和 {

    public List<List<Integer>> pairSums(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        int i=0, j=n-1;
        while(i < j) {
            int sum = nums[i] + nums[j];
            if(target > sum) {
                i++;
            } else if(target < sum) {
                j--;
            } else {
                result.add(Arrays.asList(nums[i], nums[j]));
                i++;
                j--;
            }
        }
        return result;
    }

    @Test
    public void main() {
        int[] nums = {1, 3, 5, 6, 5, 6, 10};
        List<List<Integer>> res = pairSums(nums, 11);
        for (List<Integer> re : res) {
            System.out.println(re);
        }
    }
}
